A technique is known in which when a path from a departure point to a destination point according to the map information is searched for, roads are classified into one of two or more levels depending on the road type and one level is selected therefrom. In this technique, a tentative departure point and a tentative destination point on the road network of the selected level are calculated, and a path from the departure point to the destination point is calculated by utilizing in combination the shortest path on the subject road network, a connection path from the departure point to the tentative departure point, and a connection path from the tentative destination point to the destination point. The path-searching period may be shortened by limiting the search target to roads at one level.
As path searching algorithms based on a cost, various kinds of algorithms such as Dijkstra's algorithm and the A* algorithm are known.
In Dijkstra's algorithm, a path with the lowest cost may be efficiently calculated by setting a cost to each edge between nodes and calculating a combination of edges at which the cost is relatively small as a candidate path from a beginning node to an end node.
The A* algorithm is a modified Dij kstra's algorithm for further improved efficiency. In the A* algorithm, a path with the lowest cost is searched for by adding to the cost of Dijkstra's algorithm an estimated value (heuristic value) of the cost of reaching an end node. Accordingly, the area to be searched may be narrowed down to improve the efficiency of processing.
Patent Document 1: Japanese Laid-open Patent Publication No. 06-052237
Non-patent Document 1:E. W. Dijkstra, “A Note on Two Problems In Connexion with Graphs”, Numerische Mathematik 1, pp. 269-271, 1959.
Non-patent Document 2:P. E. Hart, N.J. Nilsson, B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions of Systems Science and Cybernetics, Vol. SSC-4, No. 2, pp. 100-107, 1968.